乘法

無符號乘法

被乘數 x 乘數 = 乘積

Steps

從右到左一次取一個乘數的數字。

將被乘數乘以乘數的個位數

• 如果乘數為 1，只需將被乘數的副本放在適當的位置。
• 如果數字為 0，則將 0 放在適當的位置。

將中間乘積向較早中間乘積的左側移動一位。

乘積位數

n 位被乘數 x m 位乘數 = (n+m) 位積（忽略符號位）
我們經常想要一個 32 位的乘積，因為將兩個 32 位數字相乘。
=> 必須溢出複制。

乘法算法和硬件的順序版本

• 乘法硬件的第一個版本
  • 乘數在 32 位乘數寄存器中。
  • 64 位 Product 寄存器初始化為 0。
  • 64 位被乘數寄存器用右半部分的 32 位被乘數和左半部分的 0 初始化。
  • 乘法器寄存器每步右移 1 位。
  • 被乘數寄存器每步左移 1 位，以使被乘數與 64 位乘積寄存器中累積的和對齊。

每個位需要三個基本步驟

第一步：乘法器的LSB判斷被乘數是否加到Product寄存器中。

第二步：被乘數寄存器左移具有將中間操作數向左移動的效果。

第三步：乘法器寄存器的右移給出乘法器的下一位，以便在接下來的迭代中檢查
以上步驟重複32次。

以上三步重複32次即可得到乘積
如果每一步都需要一個時鐘週期，那麼這個算法需要將近 100 個時鐘週期才能將兩個 32 位數字相乘。

參考資料 : 上課PPT